package 链表.单向链表;

/*
 * 不带哨兵位的单向非循环链表
 * */
class Test {
    public static void main(String[] args) {
        SingleListDemo list = new SingleListDemo();
        list.addTail(1);
        list.addTail(2);
        list.addTail(2);
        list.addTail(3);
        list.addTail(4);
        list.addTail(5);

    }
}

public class SingleListDemo {
    private Node head;

    public SingleListDemo() {
    }


    public void Delete(int Data) {
        if (head == null) {
            return;
        }
        while (head.val == Data) {
            head = head.next;
            if (head == null) {
                return;
            }
        }
        Node cur = head;// 定义临时节点代替头结点遍历链表并删除元素
        while (true) {
            if (cur.next == null) {
                return;
            }

            if (cur.next.val == Data) {
                System.out.println("删除成功!");
                cur.next = cur.next.next;
                continue;
            }
            cur = cur.next;
        }

    }

    // 法二 - 双指针
    public void Delete2(int Data) {
        if (head == null) {
            return;
        }
        Node pre = head;
        Node cur = head.next;

        while (cur != null) {
            if (cur.val == Data) {
                pre.next = cur.next;
            } else {
                pre = cur;
            }
            cur = cur.next;
        }
        if (head.val == Data) {
            head = head.next;
        }
    }


    public void addTail(int val) {
        Node newNode = new Node(val);

        if (head == null) {
            head = newNode;
            return;
        }

        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }

        cur.next = newNode;
    }



    // 尾删
    public void TailDelete() {


    }

    // 头删
    public void HeadDelete() {
        if (head == null) {
            System.out.println("链表为空!");
        }
        head = head.next;
    }

    // 头插
    public void HeadAdd(int val) {
        Node node = new Node(val);
        node.next = head;
        head = node;
    }

    // 在指定位置插入节点,第一个节点为0号下标
    public void InsertAny(int index, int val) {
        // 判断链表下标是否合法
        if (index < 0 && index > getSize()) {
            System.out.println("下标不合法!");
            return;
        }
        if (index == 0) {
            HeadAdd(val);
            return;
        }
        Node node = new Node(val);
        Node cur = head;
        // 遍历链表找到下标为index-1的元素
        while (index > 1) {//index-1
            index--;
            cur = cur.next;
        }
        node.next = cur.next;
        cur.next = node;
    }

    // 链表元素个数
    public int getSize() {
        Node node = head;
        int size = 0;
        while (node != null) {
            node = node.next;
            size++;
        }
        return size;
    }



    // 删除节点的Data值为key的第一个节点
    public void DeleteKey(int key) {
        // 判断链表是否为空
        if (head == null) {
            System.out.println("链表为空");
            return;
        }
        // 判断第一个节点是否是要删除的节点
        if (head.val == key) {
            HeadDelete();
            return;
        }
        Node cur = head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                cur.next = cur.next.next;
                return;
            }
            cur = cur.next;
        }
    }


}


class Node {
    public int val;
    public Node next;

    public Node(int val) {
        this.val = val;
    }
}
